#include <stdio.h>   // 提供输入输出函数，如 printf、scanf
#include <stdlib.h>  // 提供内存分配函数，如 malloc、free

// step 1# 定义哈希表节点结构体，存储键值对
typedef struct {
    int key;         // 键，表示数组中的某个值
    int value;       // 值，表示该值在数组中的索引
} HashNode;

// step 2# 哈希函数：将整数 key 映射到哈希表索引
int hashFunction(int key, int hashSize) {
    long long tmp = (long long)key;  // 防止溢出，转为长整型
    if (tmp < 0) tmp = -tmp;         // 保证哈希值为正
    return tmp % hashSize;           // 取模作为哈希索引
}

// step 3# 实现两数之和主函数
int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
    // step 3.1# 初始化哈希表大小为原数组长度的两倍，减少冲突
    int hashSize = numsSize * 2;
    HashNode *hashTable = (HashNode *)malloc(sizeof(HashNode) * hashSize); // 分配哈希表空间

    // step 3.2# 初始化哈希表，所有位置设置为空（value = -1 表示未使用）
    for (int i = 0; i < hashSize; i++) {
        hashTable[i].key = 0;
        hashTable[i].value = -1;
    }

    // step 3.3# 遍历数组，查找每个元素的补数
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];                       // 计算目标补数
        int comIndex = hashFunction(complement, hashSize);      // 计算补数在哈希表中的索引

        // step 3.4# 查找补数是否已经存在于哈希表中
        while (hashTable[comIndex].value != -1) {               // 哈希表当前位置非空
            if (hashTable[comIndex].key == complement) {        // 找到补数
                int *res = (int *)malloc(sizeof(int) * 2);      // 分配返回结果数组
                res[0] = i;                                     // 当前元素下标
                res[1] = hashTable[comIndex].value;             // 补数元素下标
                *returnSize = 2;                                // 设置返回数组大小
                return res;                                     // 返回结果
            }
            comIndex = (comIndex + 1) % hashSize;               // 发生哈希冲突，线性探测
        }

        // step 3.5# 将当前元素插入哈希表中
        int numsIndex = hashFunction(nums[i], hashSize);        // 计算当前元素的哈希索引
        while (hashTable[numsIndex].value != -1) {              // 如果当前位置已被占用
            numsIndex = (numsIndex + 1) % hashSize;             // 线性探测寻找空位
        }
        hashTable[numsIndex].key = nums[i];                     // 存储当前值作为 key
        hashTable[numsIndex].value = i;                         // 存储当前索引作为 value
    }

    // step 3.6# 如果未找到任何一组满足条件的数，返回 NULL
    *returnSize = 0;                                            // 设置返回结果大小为 0
    return NULL;
}
